package club.xiaojiawei.binarytree;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/17/22 11:58 PM
 * @question 530. 二叉搜索树的最小绝对差
 * @description 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 * 差值是一个正数，其数值等于两值之差的绝对值。
 */
public class GetMinimumDifference530 {

    public static void main(String[] args) {
        GetMinimumDifference530 test = new GetMinimumDifference530();
        TreeNode root = new TreeNode(1, null, new TreeNode(3, new TreeNode(2), null));
        int result = test.getMinimumDifference(root);
        System.out.println(result);
    }

    int min = Integer.MAX_VALUE;
    TreeNode pre = null;

    /**
     * 中序遍历
     * @param root
     * @return
     */
    public int getMinimumDifference(TreeNode root) {
        if (min == 1 || root == null){
            return min;
        }
        getMinimumDifference(root.left);
        if (pre != null && Math.abs(pre.val - root.val) < min){
            min = Math.abs(pre.val - root.val);
        }
        pre = root;
        getMinimumDifference(root.right);
        return min;
    }

    int pre2;
    int ans;

    /**
     * 官方-中序遍历
     * @param root
     * @return
     */
    public int getMinimumDifference2(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre2= -1;
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (pre2 != -1) {
            ans = Math.min(ans, root.val - pre2);
        }
        pre2 = root.val;
        dfs(root.right);
    }
    
    private int minDiff = Integer.MAX_VALUE;

    private int preValue = 10000;

    public void update(TreeNode node){
        minDiff = Math.min(minDiff, Math.abs(preValue - node.val));
        preValue = node.val;
    }

    /**
     * morris中序遍历
     * @param root
     * @return
     */
    public int getMinimumDifference3(TreeNode root) {
        TreeNode cur = root, morris;
        go:
        while (cur != null){
            morris = cur.left;
            if (morris != null){
                while (true){
                    if (morris.right == null){
                        morris.right = cur;
                        cur = cur.left;
                        continue go;
                    }else if (morris.right == cur){
                        morris.right = null;
                        break;
                    }
                    morris = morris.right;
                }
            }
            update(cur);
            cur = cur.right;
        }
        return minDiff;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
